package com.demo.java.OD601_650.OD649;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌(全网一个名)
 * @Source 公众号：猿圈奇妙屋
 * @des： 【构建二叉树(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/147037540
 */
public class OdMain {

    // 二叉树节点类的定义
    private static class treeNode {
        int data;          // 节点的数据
        treeNode left;     // 左子节点
        treeNode right;    // 右子节点

        // 构造函数，用于初始化节点的数据
        public treeNode(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        // 创建一个扫描器对象，接收用户的输入
        Scanner in = new Scanner(System.in);

        // 输入格式示例：[0, 1], [0, 2] 表示对根节点的左右子节点进行操作
        String[] input_infos = in.nextLine().replace("[", "").replace("]", "").split(",");

        // 创建一个二维数组来保存操作信息，operations[i][0]表示层级，operations[i][1]表示父节点的索引
        Integer[][] operations = new Integer[input_infos.length / 2][2];

        // 遍历输入数组，将操作信息分成层级和索引
        for (int i = 0; i < input_infos.length; i++) {
            if (i % 2 == 0) {
                operations[i / 2][0] = Integer.parseInt(input_infos[i].trim());  // 获取层级信息
                operations[i / 2][1] = Integer.parseInt(input_infos[i + 1].trim());  // 获取索引信息
            }
        }

        // 初始化根节点，data为-1（即根节点）
        treeNode head = new treeNode(-1);

        // 保存每层节点的列表，根节点位于第0层
        ArrayList<treeNode> first_level = new ArrayList<>();
        first_level.add(head);

        // 创建一个数组列表用于保存每层的节点，初始化第一层
        ArrayList<ArrayList<treeNode>> tree = new ArrayList<ArrayList<treeNode>>() {{
            add(first_level);  // 第0层只有根节点
        }};

        // 根据操作数组逐步构建二叉树
        for (int i = 0; i < operations.length; i++) {
            int height = operations[i][0];  // 当前操作节点所在的层级
            int index = operations[i][1];   // 当前操作节点的父节点索引

            // 如果树中不存在当前层级的节点列表，就新建
            if (tree.size() <= height + 1) {
                tree.add(new ArrayList<>());
            }

            // 创建一个新的节点，并加入到对应层级的列表中
            treeNode temp_node = new treeNode(i);
            tree.get(height + 1).add(temp_node);

            // 获取父节点，判断是给左子节点还是右子节点赋值
            treeNode parent_node = tree.get(height).get(index);
            if (parent_node.left == null) {
                parent_node.left = temp_node;  // 如果左子节点为空，插入左子节点
            } else if (parent_node.right == null) {
                parent_node.right = temp_node; // 如果右子节点为空，插入右子节点
            }
        }

        // 层序遍历二叉树
        LinkedList<Integer> result = new LinkedList<>();
        LinkedList<treeNode> queue = new LinkedList<>();

        // 将根节点加入队列进行层序遍历
        queue.add(tree.get(0).get(0));

        // 当队列不为空时，继续遍历
        while (queue.size() > 0) {
            treeNode node = queue.removeFirst();  // 从队列中移除并获取一个节点

            if (node != null) {
                result.add(node.data);  // 将当前节点的值添加到结果中
                queue.add(node.left);    // 将左子节点加入队列
                queue.add(node.right);   // 将右子节点加入队列
            } else {
                result.add(null);        // 如果节点为空，表示这一层已经遍历到空节点，加入null
            }
        }

        // 去除结果中的末尾多余的null值
        while (true) {
            if (result.getLast() == null) {
                result.removeLast();   // 删除末尾的null值
            } else {
                break;  // 如果没有多余的null，退出循环
            }
        }

        // 输出结果
        String output_str = "[";

        // 将结果中的节点值转成字符串并拼接
        for (int i = 0; i < result.size(); i++) {
            if (result.get(i) == null) {
                output_str += "null";
            } else {
                output_str += Integer.toString(result.get(i));
            }

            if (i != result.size() - 1) {
                output_str += ",";  // 添加逗号分隔符
            }
        }

        output_str += "]";

        // 打印最终的层序遍历结果
        System.out.println(output_str);
    }
}
